class Solution {
public:
    /*
    dp[i],表示到第i个字符的时候(包含第i个字符)，是否可以被拼接
    [0, i]的字符可以被分为两部分：[j, i]和[0, j - 1]
    [0, j - 1]的字符是否可以被拼接可以由dp表直接求出
    [j, i]的字符是否可以被拼接，在字典中查询即可
    如果两部分的字符都可以被拼接，说明[0, i]的字符就可以被拼接
    */
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> s_set;
        for (auto& i : wordDict)
            s_set.insert(i);
            
        vector<bool> dp(n + 1, true);
        for (int i = 1; i < n + 1; ++i)
        {
            for (int j = i; j >= 1; --j)
            {
                string tmp = s.substr(j - 1, i - j + 1);
                dp[i] = dp[j - 1] && s_set.count(tmp);
                if (dp[i])
                    break;
            }
        }
        
        return dp[n];
    }
};